package com.mdnote.practice.dp;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description 01背包
 */
public class Package01 {

    public static void main(String[] args) {

        int[] weight = {1, 3, 4};
        int[] price = {1500, 2000, 3000};

        int packageSize = 5;

        int res = solute(weight, price, packageSize);

        System.out.println(res);
    }

    /**
     * 01背包问题
     * 1. 状态：当前需要选择的物品i，当前背包容量，dp[i][j]当前的背包的总价值
     * 2. DP方程  dp[i][j] = Math.max(不放入物品I，放入武平I)
     *                     = Math.max(dp[i - 1][j], dp[i - 1][j - weighti] + price[i])
     * 3. base case: dp[0][j] 不放入任何物品容量为j的背包价格 = 0
     *              dp[i][0] 容量为0，不能放入任意物品 = 0
     * @param weight
     * @param price
     * @param packageSize
     * @return
     */
    private static int solute(int[] weight, int[] price, int packageSize) {

        int[][] dp = new int[weight.length + 1][packageSize + 1];

        // base case
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (j - weight[i - 1] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + price[i - 1]);
                } else {
                    // 放不小
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[weight.length][packageSize];
    }
}
